{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 第7章-支持向量机-最大间隔分离超平面存在唯一性\n",
    "&emsp;&emsp;最大分离超平面是由一个最优化问题得到的，最优化问题为：$$\n",
    "\\begin{array}{ll}\n",
    "\\displaystyle \\min_{w,b} & \\displaystyle \\frac{1}{2}\\|w\\|^2 \\\\ \n",
    "\\text { s.t. } & y_i(w \\cdot x_i+b)-1 \\geqslant 0\n",
    "\\end{array}$$  \n",
    "存在并且最优解是唯一的。  \n",
    "&emsp;&emsp;记最优解为$w^*,b^*$，证明过程分为两个部分，第一部分是存在性，这一部分比较简单就略过了。第二部分是唯一性，用的是反证法。首先假设最优解不是唯一的，两个解分别为$(w_1^*,b_1^*),(w_2^*,b_2^*)$，推导$w_1^*=w_2^*,b_1^*=b_2^*$，这样就可以证明最优解是唯一的。  \n",
    "### 证明  \n",
    "已知$w_1^*,w_2^*$都是最优化问题的解  \n",
    "$\\therefore \\|w_1^*\\|=\\|w_2^*\\|=c，c是一个常数$  \n",
    "构造另一组解：$\\displaystyle w=\\frac{w_1^*+w_2^*}{2},b=\\frac{b_1^*+b_2^*}{2}$  \n",
    "现假设$w_1^*,b_1^*,w_2^*,b_2^*$都已经求出，可得$w,b$都是确定的。  \n",
    "\n",
    "#### 首先需要验证$w,b$是否满足约束条件\n",
    "约束条件：$\\displaystyle y_{i}(\\frac{w_1^*+w_2^*}{2} \\cdot x_i+\\frac{b_1^*+b_2^*}{2})-1 \\geqslant 0$  \n",
    "$\\begin{aligned} {\\therefore \\quad} & y_{i}(\\frac{w_1^*+w_2^*}{2} \\cdot x_i+\\frac{b_1^*+b_2^*}{2})-1 \\\\ \n",
    "= & \\frac{1}{2}\\big[\\big(y_i(w_1^* \\cdot x_i + b_1^*) -1 \\big)+\\big(y_i(w_2^* \\cdot x_i + b_2^*) -1\\big)\\big] \n",
    "\\end{aligned}$  \n",
    "$\\because w_1^*,b_1^*,w_2^*,b_2^*$满足约束条件  \n",
    "$y_i(w_1^* \\cdot x_i + b_1^*) -1 \\geqslant 0, y_i(w_2^* \\cdot x_i + b_2^*) -1 \\geqslant 0$  \n",
    "$\\displaystyle \\therefore y_{i}(\\frac{w_1^*+w_2^*}{2} \\cdot x_i+\\frac{b_1^*+b_2^*}{2})-1 \\geqslant 0$  \n",
    "可得$w,b$在可行域中，满足所有的$N$个约束条件  \n",
    "\n",
    "#### 证明$w_1^*=w_2^*$\n",
    "易得$\\|w_1^*\\| \\leqslant \\|w\\|$，不然$w_1^*$就不是最优解了。  \n",
    "$\\displaystyle \\therefore c \\leqslant \\|w\\| = \\|\\frac{1}{2} w_1^*+ \\frac{1}{2} w_2^*\\|$  \n",
    "根据**三角不等式** $\\displaystyle \\|\\frac{1}{2} w_1^*+ \\frac{1}{2} w_2^*\\| \\leqslant \\frac{1}{2}\\|w_1^*\\|+\\frac{1}{2}\\|w_2^*\\|$  \n",
    "$\\displaystyle \\therefore c \\leqslant \\|w\\| = \\|\\frac{1}{2} w_1^*+ \\frac{1}{2} w_2^*\\| \\leqslant \\frac{1}{2}\\|w_1^*\\|+\\frac{1}{2}\\|w_2^*\\| = c$  \n",
    "根据**夹逼定理** $\\displaystyle \\|\\frac{1}{2} w_1^*+ \\frac{1}{2} w_2^*\\| = \\frac{1}{2}\\|w_1^*\\|+\\frac{1}{2}\\|w_2^*\\|$  \n",
    "根据**向量相加原理** ，只有$w_1^*$与$w_2^*$是同方向的，才能满足上式。  \n",
    "$\\therefore w_1^*=\\lambda w_2^*, \\lambda \\geqslant 0$  \n",
    "$\\because \\|w_1^*\\|=\\|w_2^*\\|=c$  \n",
    "$\\therefore \\lambda = 1$  \n",
    "$\\therefore w_1^*=w_2^*$  \n",
    "\n",
    "#### 证明$b_1^* = b_2^*$\n",
    "可以把两个最优解写成$(w^*, b_1^*),(w^*, b_2^*)$  \n",
    "&emsp;&emsp;先观察在最优化问题中$b$出现的位置，可以看到$b$出现在不等式约束中，假如想找到一个关于$b$的等式，那就需要寻找使得不等式约束变成等式约束的那些约束。  \n",
    "&emsp;&emsp;那什么时候是等式约束呢？位于支撑超平面上的点就可以满足等式约束，目前有两个最优解，就有两个不同的分离超平面，由于$w$是相同的，就表示斜率是一样的，但是$b_1^*$和$b_2^*$不同，这两个平面有不同的位置（平移关系），这两个分离超平面都会各有两个支撑超平面。  \n",
    "&emsp;&emsp;在$(w,b_1^*)$中，正类+1的点记为$x_1'$，负类-1的点记为$x_1''$，在$(w,b_2^*)$中，正类+1的点记为$x_2'$，负类-1的点记为$x_2''$，可知$x_2'$位于一个支撑超平面（正类+1）上方，$x_2''$位于一个支撑超平面（负类-1）下方，同理$x_1'$位于一个支撑超平面（正类+1）上方，$x_1''$位于一个支撑超平面（负类-1）下方。  \n",
    "由于$x_1'$与$x_2'$在同一个支撑超平面（正类+1）上  \n",
    "$\\therefore w^* \\cdot x_1' + b_1^* - 1 = 0, w^* \\cdot x_2' + b_1^* - 1 \\geqslant 0$  \n",
    "$\\therefore w^* \\cdot x_1' \\leqslant w^* \\cdot x_2'$  \n",
    "$\\therefore w^* \\cdot x_2' + b_2^* - 1 = 0, w^* \\cdot x_1' + b_2^* - 1 \\geqslant 0$  \n",
    "$\\therefore w^* \\cdot x_2' \\leqslant w^* \\cdot x_1'$   \n",
    "根据$w^* \\cdot x_1' \\leqslant w^* \\cdot x_2'$和$w^* \\cdot x_2' \\leqslant w^* \\cdot x_1'$，可得$w^* \\cdot (x_1' - x_2') = 0$，同理可得$w^* \\cdot (x_1'' - x_2'') = 0$  \n",
    "$\\because \\begin{array}{l} w^* \\cdot x_1' + b_1^* - 1 = 0 \\\\ \n",
    "-(w^* \\cdot x_1'' + b_1^*) - 1 = 0 \\end{array}$  \n",
    "$\\therefore \\begin{array}{l} b_1^*=1-w * \\cdot x_1' \\\\ \n",
    "b_1^* = -1 - w * \\cdot x_1''\n",
    "\\end{array}$  \n",
    "$\\displaystyle \\therefore b_1^* = \\frac{1}{2} (w^* \\cdot x_1' + w^* \\cdot x_1'')$  \n",
    "同理可得$\\displaystyle b_2^* = \\frac{1}{2} (w^* \\cdot x_2' + w^* \\cdot x_2'')$\n",
    "由于需要证明$b_1^* = b_2^*$，故求$b_1^* - b_2^* = 0$  \n",
    "$\\displaystyle \\therefore b_1^* - b_2^* = -\\frac{1}{2}[w^* \\cdot (x_1' - x_2') + w^* \\cdot (x_1'' - x_2'')]$  \n",
    "$\\because w^* \\cdot (x_1' - x_2') = 0, w^* \\cdot (x_1'' - x_2'') = 0$  \n",
    "$\\displaystyle \\therefore -\\frac{1}{2}[w^* \\cdot (x_1' - x_2') + w^* \\cdot (x_1'' - x_2'')] = 0$  \n",
    "$\\therefore b_1^* - b_2^* = 0$ 即 $b_1^* = b_2^*$  \n",
    "\n",
    "#### 结论 \n",
    "根据$w_1^*=w_2^*$，$b_1^* = b_2^*$，可得两个最优解$(w_1^*, b_1^*),(w_2^*, b_2^*)$是相同的，解的唯一性得证。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
